package leetcode.code0854;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	int len, limit;
	char[] cs1, cs2;

	public int kSimilarity(String s1, String s2) {
		len = s1.length();
		this.cs1 = s1.toCharArray();
		this.cs2 = s2.toCharArray();
		limit = (1 << len) - 1;
		int cur = 0;
		for (int i = 0; i < len; i++) {
			if (s1.charAt(i) == s2.charAt(i)) {
				cur |= 1 << i;
			}
		}
		Integer[][] dp = new Integer[1 << len][2];
		int ans = this.f(cur, 0, dp);
		return ans;
	}

	private int f(int cur, int k, Integer[][] dp) {
		if (cur == limit) {
			return k;
		}
		if (dp[cur] != null && dp[cur][1] != null && k >= dp[cur][1]) {
			return dp[cur][0];
		}
//		System.out.println(cur + " " + k);
		int ans = 20;
		for (int i = 0; i < len; i++) {
			if ((cur & (1 << i)) == 0) {
				for (int j = i + 1; j < len; j++) {
					if (((cur & (1 << j)) == 0) && cs1[j] == cs2[i]) {
						cur = this.swap1(cs1, i, j, cs2, cur);
						int ans1 = this.f(cur, k + 1, dp);
						ans = Math.min(ans, ans1);
						cur = this.swap2(cs1, i, j, cs2, cur);
					}
				}
			}
		}
		dp[cur][0] = ans;
		dp[cur][1] = k;
		return ans;
	}

	private int swap1(char[] cs1, int i, int j, char[] cs2, int status) {
		if (cs2[i] == cs1[j]) {
			status |= 1 << i;
		}
		if (cs1[i] == cs2[j]) {
			status |= 1 << j;
		}
		this.swap(cs1, i, j);
		return status;
	}

	private int swap2(char[] cs1, int i, int j, char[] cs2, int status) {
		if (cs2[i] == cs1[i]) {
			status ^= 1 << i;
		}
		if (cs1[j] == cs2[j]) {
			status ^= 1 << j;
		}
		this.swap(cs1, i, j);
		return status;
	}

	private void swap(char[] cs12, int i, int j) {
		char c = cs12[i];
		cs12[i] = cs12[j];
		cs12[j] = c;
	}

	@Override
	public void debug4() {
		H.compare(9, this.kSimilarity("aaaabbbbccccddddeeee", "edcbaacbcebcdbeedaad"));
//		H.compare(9, this.kSimilarity("abccaacceecdeea", "bcaacceeccdeaae"));
//		H.compare(6, this.kSimilarity("aabbccddee", "cdacbeebad"));
//		H.compare(2, this.kSimilarity("abcde", "ebdca"));
//		H.compare(9, this.kSimilarity("abcabcdefabcdef", "faebacbbdafdecc"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
